package com.java.comprehensive.arithmetic.leecode.easy;

/**
 * @program: comprehensive-service
 *
 * @description: 实现strStr()函数
 *
 * @author: 窦绍飞
 *
 * @create: 2021-11-18 11:42
 **/
public class LeetCode_28 {

	public static int strStr(String haystack, String needle) {
		if (haystack.length() == 0 && needle.length() == 0)
			return 0;
		int j = needle.length();
		int b;
		for (int i = 0; i < haystack.length(); i++) {
			if (i + j <= haystack.length()) {
				String substring = haystack.substring(i, i + j);
				if (needle.equals(substring)) {
					b = i;
					return b;
				}
			}
		}
		return -1;
	}

	// 暴力匹配（伪码）
	public static int search(String haystack, String needle) {
		int M = needle.length();
		int N = haystack.length();
		for (int i = 0; i <= N - M; i++) {
			int j;
			for (j = 0; j < M; j++) {
				if (needle.charAt(j) != haystack.charAt(i + j)) {
					break;
				}
			}
			// pat 全都匹配了
			if (j == M) {
				return i;
			}
		}
		// txt 中不存在 pat 子串
		return -1;
	}

	public static void main(String[] args) {
		String haystack = "sadbutsad", needle = "sad";
		int i = strStr(haystack, needle);
		System.out.println(i);
		int search = search(haystack, needle);
		System.out.println(search);

	}
}
